package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import LeetCode.interview._104_Maximum_Depth_of_Binary_Tree.TreeNode;
import sun.net.www.content.text.plain;
import sun.tools.jar.resources.jar;
import util.LogUtils;

/*
 * 
原题　
		We are playing the Guess Game. The game is as follows:
	
	I pick a number from 1 to n. You have to guess which number I picked.
	
	Every time you guess wrong, I'll tell you whether the number is higher or lower.
	
	You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):
	
	-1 : My number is lower
	 1 : My number is higher
	 0 : Congrats! You got it!
	
	Example:
	
	n = 10, I pick 6.
	
	Return 6.

题目大意
	猜数字游戏,程序预先定义了一个guess方法, 返回-1,1,0
解题思路
	....这题目看着都像二分法......
 * @Date 2017-10-01 11：20
 */
public class _374_Guess_Number_Higher_or_Lower {
	/**
	 * @My:
	 * @param n
	 * @return
	 */
	/* The guess API is defined in the parent class GuessGame.
	   @param num, your guess
	   @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
	      int guess(int num); */
    public int guessNumber(int n) {
    	if (guess(n) == 0)	return n;
    	int l = 0, r = n;			//二分查找
    	while (l < r) {
    		int mid = l + (r-l)/2;				//注：不能使用 mid=(l+r)/2  原因：LeetCode丧心病狂的long类型测试用例,会越界！！！
    		int rsTemp = guess(mid);
    		if (rsTemp > 0)	{		//return 1
    			l = mid;
    		} else if (rsTemp < 0) {
    			r = mid;
    		} else {
    			return mid;
    		}
    	}
        return 0;
    }
    /*
     * 该方法由系统定义
     */
    private int guess(int n) {
    	return 10 - n;
    }
    
	public static void main(String[] args) {
		_374_Guess_Number_Higher_or_Lower obj = new _374_Guess_Number_Higher_or_Lower();
		LogUtils.println("374", obj.guessNumber(70));
	}

}
